package middle;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class Solution_398 {

    static class Solution {

        private Random random = new Random();
        private int[] arrays;

        public Solution(int[] nums) {
            arrays = nums;
        }

        public int pick(int target) {
            int index = -1, count = 0;
            for (int i = 0; i < arrays.length; i++) {
                if (arrays[i] == target) {
                    count++;
                    int n = random.nextInt(count);
                    if (n == 0) {
                        index = i;
                    }
                }
            }
            return index;
        }
    }

    static class Solution_1 {

        private Random random = new Random();
        private Map<Integer, List<Integer>> map;

        public Solution_1(int[] nums) {
            map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                List<Integer> list = map.computeIfAbsent(nums[i], k -> new ArrayList<>());
                list.add(i);
            }
        }

        public int pick(int target) {
            List<Integer> list = map.get(target);
            if (list == null || list.size() == 0) {
                return -1;
            }
            return list.get(random.nextInt(list.size()));
        }
    }
}
